class Solution {
public:
    Solution() { init(); }
    void init() {
        a = vector<vector<int>>(10);
        a[0] = {4, 6};
        a[1] = {8, 6};
        a[2] = {7, 9};
        a[3] = {4, 8};
        a[4] = {0, 3, 9};
        a[5] = {};
        a[6] = {0, 1, 7};
        a[7] = {2, 6};
        a[8] = {1, 3};
        a[9] = {2, 4};
    }
    int knightDialer(int n) {
        vector<int> newmap(10, 1);
        while (--n) {
            vector<int> tmpmap(10);
            for (int i = 0; i < 10; i++) {
                for (int j : a[i]) {
                    tmpmap[j] = (tmpmap[j] + newmap[i]) % nn;
                }
            }
            swap(tmpmap, newmap);
        }
        int ans = 0;
        for (int i : newmap) {
            ans = (ans + i) % nn;
        }
        return ans;
    }
    vector<vector<int>> a;
    int nn = 1e9 + 7;
};